package com.ting.test.algorithms.图;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

/**
 * 特点：有向无负
 */
public interface 迪瑞克斯拉算法_加强堆 {
    public static void main(String[] args) {
        process(new Node(3));
        Integer[] arr = new Integer[]{2, 5, 9, 4, 1, 8, 24, 8};
//        Integer[] result = smallHeap(arr);
    }

    static void process(Node node) {
        HeapGreater heapGreater = new HeapGreater(node);
        Node popNode = heapGreater.popFirst();
        for (Edge edge : popNode.edges) {
            Node to = edge.getTo();


        }
    }


    /**
     * 普通堆的缺陷在于只能从堆顶或者堆底进行调整
     * 无法从堆的某一个位置进行调整
     */
    class HeapGreater {
        ArrayList<Record> heap = new ArrayList<>();
        HashMap<Record, Integer> indexMap = new HashMap<>();
        HashMap<Node, Record> indexNodeRecordMap = new HashMap<>();
        int heapSize = 0;

        public HeapGreater(Node node) {
            Record record = new Record(node, 0);
            heap.add(record);
            indexNodeRecordMap.put(node, record);
            indexMap.put(record, 0);
            heapSize++;

        }


        /**
         * 插入的时候从堆底插入
         *
         * @param record
         */
        public void insertOrUpdate(Node node, Integer distance) {
            indexNodeRecordMap.get(node);
            Record record = new Record(node, distance);
            heap.add(record);
            indexNodeRecordMap.put(node, record);
            indexMap.put(record, heapSize);
            heapSize++;
            int parent = (heapSize - 1) / 2;
            while (parent >= 0) {
                if (record.distance < heap.get(parent).distance) {
                    swap(heapSize - 1, parent);
                }
            }
        }


        /**
         * 插入的时候从堆底插入
         *
         * @param record
         */
        public void heapInsert(Node node, Integer distance) {
            Record record = new Record(node, distance);
            heap.add(record);
            indexNodeRecordMap.put(node, record);
            indexMap.put(record, heapSize);
            heapSize++;
            int parent = (heapSize - 1) / 2;
            while (parent >= 0) {
                if (record.distance < heap.get(parent).distance) {
                    swap(heapSize - 1, parent);
                }
            }
        }


        public Node popFirst() {
            Node node = heap.get(0).node;
            swap(0, heapSize - 1);
            heap.remove(--heapSize);
            indexMap.remove(indexNodeRecordMap.get(node));
            indexNodeRecordMap.remove(node);
            pop(0);//调整堆
            return node;
        }

        /**
         * 弹出指定元素先
         *
         * @return
         */
        public void pop(int index) {
            int left = index * 2 + 1;
            int small = 0;
            while (left < heapSize) {
                if (left + 1 < heapSize) {
                    small = heap.get(left).distance < heap.get(left + 1).distance ? left : left + 1;
                } else {
                    small = left;
                }
                //如果当前节点的位置已经满足小顶堆 则直接退出
                if (heap.get(index).distance < heap.get(small).distance) {
                    break;
                }
                swap(index, small);
                index = small;
                left = index * 2 + 1;
            }
        }

        public boolean isInHeap(Node node) {
            return indexNodeRecordMap.get(node) != null;
        }

        private void swap(int left, int right) {
            Record record = heap.get(left);
            Record recordRight = heap.get(right);
            heap.set(left, heap.get(right));
            heap.set(right, record);
            indexMap.put(record, right);
            indexMap.put(recordRight, left);
        }
    }

    class Record {
        Node node;//表示节点
        int distance;//当前节点Node到顶点head的距离

        public Record(Node node, int distance) {
            this.node = node;
            this.distance = distance;
        }

        public Node getNode() {
            return node;
        }

        public int getDistance() {
            return distance;
        }
    }


}
